{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recurrent Neural Network: Training Issues\n",
    "\n",
    "\n",
    "In this notebook, we discuss two topics.\n",
    "\n",
    "- Various issues related to training RNNs, i.e., vanishing & exploding gradient problem\n",
    "- Techniques to resolve vanishing & exploding gradient problem\n",
    "\n",
    "We use the formulas for the loss gradients that we derived from RNN training in this discussion.\n",
    "\n",
    "\n",
    "## Loss Gradients\n",
    "\n",
    "The formulas for computing loss gradients w.r.t. to the three weight matrices are given below.\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hy}} = \\sum_{t = 0}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(o_t)] \\vec{h}_t$\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} = \\sum_{t = 1}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(\\vec{o}_t)] \\pmb{W}_{hy} \\sum_{i=1}^t(\\prod_{j=i+1}^t \\phi^{'} \\otimes (.) \\pmb{W}_{hh}) [\\phi^{'}\\otimes(\\vec{z}_i)]\\vec{h}_{i-1}$\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{xh}} = \\sum_{t = 1}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(\\vec{o}_t)] \\pmb{W}_{hy} \\sum_{i=1}^t(\\prod_{j=i+1}^t \\phi^{'} \\otimes (.) \\pmb{W}_{hh}) [\\phi^{'}\\otimes(\\vec{z}_i)]\\vec{x}_{i}$\n",
    "\n",
    "These loss gradients are computed at each timestep, and are used to update the model parameters starting from timestep $T$ in the backward direction up to timestep $0$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Training Issues in RNN\n",
    "\n",
    "Let's analyze the loss gradients w.r.t. $\\pmb{W}_{hh}$ and $\\pmb{W}_{xh}$. For any timestep, these two loss gradients are based on the product of $\\pmb{W}_{hh}$ and the derivative of the activation function, starting from the beginning of the sequence up to the current timestep. It's the mathematical illustration of the fact that hidden state \"stores\" memory of the past sequence to infer the current output. The recurrent weights $\\pmb{W}_{hh}$ of each step represent the importance of each step towards the final prediction. \n",
    "\n",
    "- The problem is that the recurrent weights $\\pmb{W}_{hh}$ & $\\pmb{W}_{xh}$ are multiplied with the activation derivative increasingly many times as we go deeper in the past.\n",
    "\n",
    "RNNs outperform feedforward DNNs for sequence data based inference due to their ability to \"store\" past states. Ironically this very ability is a key limitation of RNNs. It is due to repeated multiplication of the past knowledge!\n",
    "\n",
    "However, this limitation surfaces when the sequence is very long (which is usually the case). It creates unstable gradients, which hinders or totally destroys the learning. Unstable gradients may occur in two ways.\n",
    "\n",
    "- Exploding Gradient\n",
    "- Vanishing Gradient\n",
    "\n",
    "Let's explain the origin of the unstable gradient problem.\n",
    "\n",
    "## Unstable Gradients: Root Cause\n",
    "\n",
    "Consider the formula for the loss gradient $\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}}$.\n",
    "\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} = \\sum_{t = 1}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(\\vec{o}_t)] \\pmb{W}_{hy} \\frac{\\partial \\vec{h}_{t}}{\\partial \\pmb{W}_{hh}}$\n",
    "\n",
    "The last term $ \\frac{\\partial \\vec{h}_t}{\\partial \\pmb{W}_{hh}}$ is computed as follows.\n",
    "\n",
    "\n",
    "$ \\frac{\\partial \\vec{h}_t}{\\partial \\pmb{W}_{hh}} = \\sum_{i=1}^t(\\prod_{j=i+1}^t \\frac{\\partial \\vec{h}_j}{\\partial \\vec{h}_{j-1}}) [\\phi^{'}\\otimes(\\vec{z}_i)]\\vec{h}_{i-1}$\n",
    "\n",
    "The root cause of the unstable gradients is the repeated multiplication $\\prod_{t=1}^T \\frac{\\partial \\vec{h}_t}{\\partial \\vec{h}_{t-1}}$. The term $\\frac{\\partial \\vec{h}_t}{\\partial \\vec{h}_{t-1}}$ itself is a product of two terms:\n",
    "\n",
    "$\\frac{\\partial \\vec{h}_t}{\\partial \\vec{h}_{t-1}} = \\phi^{'} \\otimes (\\pmb{W}_{xh} \\vec{x}_t + \\pmb{W}_{hh} \\vec{h}_{t-1} + \\vec{b}_h) \\pmb{W}_{hh}$\n",
    "\n",
    "=> $\\frac{\\partial \\vec{h}_t}{\\partial \\vec{h}_{t-1}} = \\phi^{'} \\otimes (.) \\pmb{W}_{hh}$\n",
    "\n",
    "\n",
    "We will show that due to successive product of the above product a RNN may either produce vanishingly small gradients or prohibitively large (exploding) gradients.\n",
    "\n",
    "First, let's analyze the contribution of the repeated multiplication of $\\pmb{W}_{hh}$. For a long sequence, we need to compute very large power of $\\pmb{W}_{hh}$. Depending on the **norm** of $\\pmb{W}_{hh}$, the resultant product either converges to zero or diverges. To get the norm of $\\pmb{W}_{hh}$, we compute its eigendecomposition:\n",
    "\n",
    "$\\pmb{W}_{hh} = \\pmb{V} diag(\\lambda) \\pmb{V}^{-1}$\n",
    "\n",
    "Here $\\pmb{V}$ is the eigenvector and $diag(\\lambda)$ is the diagonalized eigenvalue matrix of $\\pmb{W}_{hh}$.\n",
    "\n",
    "Taking a large power of $\\pmb{W}_{hh}$, as we do during back propagation:\n",
    "\n",
    "$\\pmb{W}_{hh}^t = (\\pmb{V} diag(\\lambda) \\pmb{V}^{-1})^t$\n",
    "\n",
    "=> $\\pmb{W}_{hh}^t = \\pmb{V} diag(\\lambda)^t \\pmb{V}^{-1}$\n",
    "\n",
    "Depending on the eigenvalues $\\lambda_i$, one of the following two things can happen.\n",
    "\n",
    "- If $\\lambda_i > 1$, then $\\pmb{W}^t$ would be exponentially large, hence the loss gradients explode.\n",
    "- If $\\lambda_i < 1$, then $\\pmb{W}^t$ would be exponentially small, hence hence the loss gradients vanish.\n",
    "\n",
    "\n",
    "\n",
    "But the $\\pmb{W}_{hh}$ term doesn't contribute alone in the repeated multiplication in $\\prod_{t=1}^T \\frac{\\partial \\vec{h}_t}{\\partial \\vec{h}_{t-1}}$. We need to account for the derivative of the nonlinear activation term as well.\n",
    "\n",
    "\n",
    "## Unstable Gradients: Effect of the Derivative of the Nonlinear Activation\n",
    "\n",
    "The derivative of the nonlinear activation function is given by the Jacobian matrix: $\\phi^{'} \\otimes (\\pmb{W}_{xh} \\vec{x}_t + \\pmb{W}_{hh} \\vec{h}_{t-1} + \\vec{b}_h)$. This term is responsible for causing the **vanishing gradient** problem. It can also cause the **exploding gradient** problem. Let’s see how it works.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "$\\prod_{t=1}^T \\phi^{'} \\otimes (\\pmb{W}_{xh} \\vec{x}_t + \\pmb{W}_{hh} \\vec{h}_{t-1} + \\vec{b}_h) \\pmb{W}_{hh}$\n",
    "\n",
    "=> $\\prod_{t=1}^T \\phi^{'} \\otimes (.) \\pmb{W}_{hh}$\n",
    "\n",
    "\n",
    "\n",
    "Depending on whether we use tanh or sigmoid as the nonlinear activation, the norm of the Jacobian is bounded by 1. Because the max derivative of tanh is 1, and for sigmoid it is 0.25, as shown below. \n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Sigmoid_Tanh.png\" width=600, height=400>\n",
    "\n",
    "The Jacobian is multiplied with $\\pmb{W}_{hh}$, the resulting product is multiplied many times through the sequence. \n",
    "\n",
    "When the activation derivative is **equal to 1** (for tanh activation) it will drive the product with $\\pmb{W}_{hh}$ to a very large value. After repeated multiplications, this value will become exponentially large causing gradient explosion. \n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_ExplodingGradient.png\" width=500, height=400>\n",
    "\n",
    "\n",
    "\n",
    "When the activation derivative is **less than 1**, it will drive the product with $\\pmb{W}_{hh}$ to a small value, which after repeated multiplications becomes vanishingly small. This could happen at the beginning of training when the weights are smaller. Thus $\\phi^{'} \\otimes (\\pmb{W}_{xh} \\vec{x}_t + \\pmb{W}_{hh} \\vec{h}_{t-1} + \\vec{b}_h)$ will give values < 1.\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_VanishingGradient.png\" width=900, height=500>\n",
    "\n",
    "\n",
    "Assuming that the nonlinear activation used is tanh and the fact that derivative of tanh is between 0 to 1, we may experience one of the following two cases.\n",
    "\n",
    "\n",
    "- |W| > 1 and $tanh^{'}(.) < 1$: successive products of these two terms will lead to zero\n",
    "- |W| < 1 and $tanh^{'}(.) \\leq 1$: successive products of these two terms will lead to zero\n",
    "\n",
    "\n",
    "\n",
    "In either case, $\\prod_{t=1}^T \\phi^{'} \\otimes (.) \\pmb{W}_{hh} \\rightarrow 0$ \n",
    "\n",
    "Also later during the training when the signals are saturated, the derivative of tanh tends to be zero, which drives the loss gradient faster to zero.\n",
    "\n",
    "\n",
    "\n",
    "As a consequence, the loss gradients become tiny. \n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} \\rightarrow 0$\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{xh}} \\rightarrow 0$\n",
    "\n",
    "Thus, there is no weight update, meaning no learning!\n",
    "\n",
    "\n",
    "$\\pmb{W}_{hh} = \\pmb{W}_{hh} - \\eta \\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} \\approx \\pmb{W}_{hh}$\n",
    "\n",
    "$\\pmb{W}_{xh} = \\pmb{W}_{xh} - \\eta \\frac{\\partial \\mathcal{L}}{\\pmb{W}_{xh}} \\approx \\pmb{W}_{xh}$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How does the vanishing gradient problem influence learning?\n",
    "\n",
    "The above illustration indicates that during back propagation, the loss gradients may become increasingly smaller as the loss signal travels towards the beginning of the sequence. This results into zero or very little update in the weights at the earlier steps. It means that signals from the beginning of a sequence don't make much influence on the later steps. As a consequence, RNNs fail to maintain long-range dependencies. This is problematic if the input sequence is very long. Let's illustrate this issue using a simple language modeling problem.\n",
    "\n",
    "Consider the sequence \"The grass is green\". The word \"green\" needs to be inferred by the RNN based on the past sequence \"The grass is\". However, in this case \"green\" primarily is determined by the previous word \"grass\", the location of which is pretty close to the \"green\" in the sequence. Thus, to infer \"green\", an RNN doesn't need to rely on long-term dependency. A short-term memory is enough to make this inference possible. As long as the previous immediate neighbor states of \"green\" are updated, the short-term memory will be retained.\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Short_Memory_1.png\" width=400, height=300>\n",
    "\n",
    "Now consider another example: \"I read Republic, it is the masterpiece of Plato\". In this sequence, the word \"Plato\" depends on a distant word \"Republic\". Thus, an RNN needs to retain the memory of the long-range states. Due to the vanishing gradient problem, the long-range states are less updated. As a consequence, RNNs are unable to retain long-term memory making inferences poor for very long sequences.\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Short_Memory_2.png\" width=900, height=500>\n",
    "\n",
    "\n",
    "\n",
    "## Preventing Exploding and Vanishing Gradient Problem in RNNs\n",
    "\n",
    "The vanishing and exploding gradient problems are fundamental to the training of deep neural networks that are composed of hierarchies of nonlinear layers. These problems stall the optimization. The key point is that when a loss signal travels through many nonlinear transformations, its gradient will either blow up exponentially fast or vanish exponentially fast. \n",
    "\n",
    "\n",
    "### Historial Note on the Research on Vanishing/Exploding Gradient Problem\n",
    "These problems were first identified by Hochreiter et al. in  1991, later by Bengio et al. in 1994, further analyzed by Hochreiter et al. in 2001. Its theoretical basis was refined by Pascanu et al. in 2012.\n",
    "\n",
    "- Hochreiter et al. (1991): https://www.bioinf.jku.at/publications/older/2604.pdf\n",
    "\n",
    "- Bengio et al. (1994): https://pdfs.semanticscholar.org/d0be/39ee052d246ae99c082a565aba25b811be2d.pdf?_ga=2.105734659.1086197744.1609608111-61836822.1606497730\n",
    "\n",
    "- Hochreiter et al. (2001): https://www.researchgate.net/publication/225182080_Learning_To_Learn_Using_Gradient_Descent\n",
    "\n",
    "- Pascanu et al. (2012): https://arxiv.org/abs/1211.5063\n",
    "\n",
    "\n",
    "\n",
    "### The Exploding Gradient Problem\n",
    "The exploding gradient problem is more common in RNNs. Due to large gradients, the weight updates are larger. As a consequence, the Backpropagation algorithm would diverge. Luckily it has an easy fix. We can monitor the gradients (e.g., via TensorBoard). If these get larger, we will see NaN values and eventually the program will crash. So, identifying gradient explosion is not too difficult. Once we identify it, we can resolve this issue by a technique called **gradient clipping**, which truncates the gradients at a pre-defined threshold. We will discuss this technique shortly.\n",
    "\n",
    "### The Vanishing Gradient Problem\n",
    "We should be more concerned about the vanishing gradient problem. Because it's not obvious when it occurs. Also, it has a deleterious effect on the learning in RNNs. Either due to the < 1 norm of $\\pmb{W}_{hh}$ or due to the < 1 value of the derivative of the activation, the weights in the lower layers stop getting updated. As a consequence, RNN fails to use the earlier states for inferring later states. In other words, when the vanishing gradient problem happens, RNNs lose long-range memory. What it is left with is only short-term memory. It makes inference based only on the recent past states. For problems that require the RNN to use longer dependency, it performs poorly. Thus, absence of long-term dependency in RNNs is a direct consequence of the vanishing gradient problem. We will discuss two key techniques to resolve the vanishing gradient problem.\n",
    "- Weight initialization & activation \n",
    "- Gated RNNs\n",
    "\n",
    "\n",
    "At first, we present some general approaches to handle the unstable gradient problem including weight initialization techniques & activations.\n",
    "\n",
    "- Suitable activation function with Glorot/He Initializer\n",
    "- Input normalization\n",
    "- Gradient clipping (for exploding gradient)\n",
    "- Identity Initialization with ReLU activation (for vanishing gradient)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suitable Activation Function with Glorot/He Initializer\n",
    "\n",
    "The choice of activation function influences the growth of the outputs.\n",
    "\n",
    "In feedforward neural networks (FNNs) we applied several techniques to control the growth of the outputs that include weight initialization technique, activation function, faster optimizers, etc. We use those same techniques in RNNs with one exception. The nonsaturating activation functions such as ReLU or its variants are not particularly useful to reduce the growth of outputs. \n",
    "\n",
    "- However, it depends on the weight initialization technique. Let’s understand why ReLU is harmful with Glorot/He initializers.\n",
    "\n",
    "\n",
    "Consider the following figure. Notice that as long as input to the ReLU function increases, the output increases. In other words, the outputs from the ReLU is unbounded. But why is this a problem?\n",
    "\n",
    "\n",
    "During the backpropagation in RNNs, let's say that the weights $\\pmb{W}_{hh}$ and $\\pmb{W}_{xh}$ are increased. During forward propagation, the increased weights will increase the hidden state output $\\vec{h_t}$. The increased $\\vec{h_t}$ will be fed back to the same recurrent layer, which uses the exact same weights from the previous step. The increased input will then be further increased at the output, and this growth will continue unconstrained at each timestep during the forward propagation. Eventually, it will lead to gradient explosion for a long input sequence due to large increase in $\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}}$.\n",
    "\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} = \\sum_{t = 1}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(\\vec{o}_t)] \\pmb{W}_{hy} \\sum_{i=1}^t(\\prod_{j=i+1}^t \\phi^{'} \\otimes (.) \\pmb{W}_{hh}) [\\phi^{'}\\otimes(\\vec{z}_i)]\\vec{h}_{i-1}$\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_ReLU.png\" width=600, height=400>\n",
    "\n",
    "To prevent the unbounded growth of outputs, we can use bounded activation functions such as tanh. As shown in the figure, the output of the tanh function is bounded by [-1, 1]. Thus, during forward propagation, the output cannot explode anymore.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Tanh.png\" width=600, height=400>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Input Normalization\n",
    "\n",
    "\n",
    "In general, in DNNs, output of one layer is fed as the input to the next layer. When the parameters of a layer change, the distribution of inputs to subsequent layers also changes. For the smooth convergence of training, it is important that the inputs across different layers preserve their norm. A useful technique for preserving the norm of the signals is **batch normalization (BN)**. In BN, we perform two steps at each iteration. First, we zero-center and normalize the mini-batch input for each feature, as shown below. Then, we scale and shift the input. Iteratively the model learns the optimal scale and mean of each of the layer’s inputs. The BN turns out to be an effective technique to avoid the vanishing gradient problem in DNNs and expedite the convergence.\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Layer_Normalization.png\" width=800, height=600>\n",
    "\n",
    "Unfortunately, BN is not very effective in RNNs. \n",
    "https://arxiv.org/abs/1510.01378\n",
    "\n",
    "\n",
    "Because in RNNs the recurrent activations of each timestep will have different statistics. Thus the scale and shift parameters will need to be **different for the same layer at every timestep**. It requires to fit a separate BN layer for each timestep. This not only makes the model more complicated, but also it forces us to store the statistics for each timestep during training. \n",
    "\n",
    "For RNNs, another normalization technique is more suitable, which is known as **layer normalization**.\n",
    "\n",
    "### Layer Normalization\n",
    "\n",
    "\n",
    "Layer normalization is very similar to BN, but instead of normalizing across the batch dimension, it normalizes across the features dimension. Like BN, Layer Normalization learns a scale and an offset parameter for each input. In RNNs, layer normalization is typically used right after the linear combination of the inputs and the hidden states.\n",
    "\n",
    "\n",
    "https://arxiv.org/abs/1607.06450\n",
    "\n",
    "In BN, the statistics are computed across the batch and are the same for each example in the batch. In contrast, in layer normalization, the statistics are computed across each feature and are independent of other examples. Thus, unlike BN, layer normalization is not a simple reparameterization of the network. \n",
    "\n",
    "\n",
    "There are several advantages of layer normalization over BN.\n",
    "\n",
    "- We can compute the required statistics on the fly, at each timestep, independently for each instance. \n",
    "\n",
    "- Unlike BN, it behaves the same way during training and testing. It does not need to use exponential moving averages to estimate the feature statistics across all instances in the training set.  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gradient Clipping (for Resolving Exploding Gradient)\n",
    "\n",
    "\n",
    "Gradient clipping is a simple **engineering trick** that can be used to alleviate the exploding gradient problem in RNNs. In 2012 Pascanu et al. put forward an interesting hypothesis about the loss function space or weight space in RNN.\n",
    "\n",
    "- When loss/error/cost gradient explodes, it also explodes the Hessian or curvature (2nd order derivative of the loss function). \n",
    "\n",
    "https://arxiv.org/abs/1211.5063\n",
    "\n",
    "It was argued that the weight space changed abruptly at the high curvature region, which looks like a \"cliff\".\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN-Cliff-Pascanu.png\" width=600, height=400>\n",
    "\n",
    "Let’s illustrate how a \"cliff\" is originated in 2D weight space of a RNN. Consider a simple RNN with a single hidden state neuron. For convenience, let's say that we have just the initial state ℎ_0 and there is no input.\n",
    "\n",
    "$h_t = w_{hh} \\sigma (h_{t-1}) + b_h$\n",
    "\n",
    "\n",
    "The loss/error surface after 50 epochs with $h_0 = 0.5$ is shown in the figure. Repeated multiplication of the weight vector for 50 epochs caused gradient explosion. The steep rise in the loss gradient results into high curvature walls in the weight space. These high curvature walls look like \"cliff\". \n",
    "\n",
    "\n",
    "At the cliff, the loss function changes abruptly. In the figure, the solid blue lines illustrate the standard trajectories that gradient descent might follow at the cliff. Thus, even with a small step size (learning hyperparameter), the Gradient Descent algorithm will overshoot.\n",
    "\n",
    "\n",
    "\n",
    "- How do we ensure that the high curvature walls don’t arise in the weight space?\n",
    "\n",
    "By ensuring that loss gradients don’t explode. This can be done by clipping the loss gradient.\n",
    "\n",
    "\n",
    "\n",
    "We can clip each component of the gradient vector or its $l_2$ norm. Pascanu et al. suggested to clip the norm $\\| \\pmb{g} \\|$ of the gradient $\\pmb{g}$ as follows:\n",
    "\n",
    "if $\\| \\pmb{g} \\| > v$:\n",
    "\n",
    "- $\\| \\pmb{g} \\|   \\leftarrow \\frac{ \\pmb{g} v}{\\| \\pmb{g} \\|} $\n",
    "\n",
    "Here $v$ is the norm threshold. \n",
    "\n",
    "\n",
    "In the figure, the dashed blue arrows show what would happen if the gradient is rescaled to a fixed size when its norm is above a threshold. Thus, gradient descent steps won’t overshoot.\n",
    "\n",
    "### Gradient Clipping: Two issues\n",
    "\n",
    "- Issue 1: Clip the norm of the gradient vector, not each component.\n",
    "\n",
    "We do this to ensure that the gradient descent direction doesn’t change. This might happen if one component of the gradient is too large. Then normalizing the gradient component wise will change its direction.\n",
    "As the large component would shrink significantly.In norm clipping, since all parameters are renormalized jointly, it ensures that each step is still in the direction of the gradient.\n",
    "\n",
    "\n",
    "- Issue 2: Finding an Optimal Norm Threshold\n",
    "\n",
    "Gradient clipping is simple and computationally efficient. But it introduces an additional hyperparameter, i.e., the norm threshold. How do we find a suitable threshold?\n",
    "\n",
    "One good heuristic for setting the threshold is to look at statistics on the average norm over a sufficiently large number of updates. It was shown based on empirical observation that values from half to ten times this average can still yield convergence. However, convergence speed can be affected.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Identity Initialization with ReLU Activation (for Resolving Vanishing Gradient)\n",
    "\n",
    "Previously we argued that ReLU causes the hidden state output to grow, which increases the loss gradients causing gradient explosion. But ReLU has one magical advantage, i.e., it constant 1 derivative.\n",
    "\n",
    "Thus ReLU could be very useful to mitigate the vanishing gradient problem as it never causes saturation. If we could ensure that the weight initializer will not increase the variance of the signals, then ReLU could be a boon.\n",
    "\n",
    "- How do we design a weight initializer that will not increase the variance of the hidden state $\\vec{h}_t$? \n",
    "\n",
    "\n",
    "Consider the following hidden state forward equations. The current hidden state $\\vec{h}_t$ is computed based on the weighted previous hidden state $\\vec{h}_{t-1}$.\n",
    "\n",
    "- Preactivation signal: $\\vec{z}_t = \\pmb{W}_{xh} \\vec{x}_t + \\pmb{W}_{hh} \\vec{h}_{t-1} + \\vec{b}_h$\n",
    "- Activation signal: $\\vec{h}_t = \\phi \\otimes \\vec{z}_t$\n",
    "\n",
    "\n",
    "<img src=\"https://cse.unl.edu/~hasan/Pics/RNN_Forward.png\" width=300, height=200>\n",
    "\n",
    "To ensure that the variance of the hidden state $\\vec{h}_t$ does not increase, we could initialize the recurrent weight matrix $\\pmb{W}_{hh}$ as an identity matrix (biases are initialized with zeros). \n",
    "\n",
    "Then, each new hidden state vector $\\vec{h}_t$ is obtained by **simply copying the previous hidden vector** $\\vec{h}_{t-1}$, adding on the effect of the current inputs and replacing all negative states by zero.\n",
    "\n",
    "\n",
    "In the absence of input, an RNN that is composed of ReLUs and initialized with the identity matrix just stays in the same state indefinitely.\n",
    "\n",
    "The identity initialization has the very desirable property that when the loss gradients for the hidden neurons are backpropagated through time they remain constant provided no extra loss-gradients are added.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "$\\frac{\\partial \\mathcal{L}}{\\pmb{W}_{hh}} = \\sum_{t = 1}^{T} \\frac{\\partial l(\\vec{y_t}, \\vec{y_t}^*)}{\\partial \\vec{y}_t} [\\phi^{'}\\otimes(\\vec{o}_t)] \\pmb{W}_{hy} \\sum_{i=1}^t(\\prod_{j=i+1}^t \\phi^{'} \\otimes (.) \\pmb{W}_{hh}) [\\phi^{'}\\otimes(\\vec{z}_i)]\\vec{h}_{i-1}$\n",
    "\n",
    "It has been shown that with right initialization of the weights, RNNs composed of ReLU are relatively easy to train and are good at combating the vanishing gradient problem, thus modeling long-range dependencies.\n",
    "\n",
    "https://arxiv.org/abs/1504.00941\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
